
/*
 * template implementation of the fixed allocation mechanism.
 * Controlled by the following macro definitions:
 *
 * required macros:
 *  QL_FIXED_ALLOC_ELEMENT_TYPE - defines element type
 *  QL_FIXED_ALLOC_XMALLOC - defines memory allocation function, that will never return 0
 *  QL_FIXED_ALLOC_XFREE - defines memory releasing function
 *
 * optional macros:
 *  QL_FIXED_ALLOC_NS - namespace macro
 *  QL_FIXED_ALLOC_FREE_FUNCTION_REQUIRED - if defined, allocator will be capable to free elements, free function will be available
 *  QL_FIXED_ALLOC_GET_ALLOCATOR_STATUS_REQUIRED - if defined, get status function will be made available
 *  QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE - defines initial chunk size in bytes for allocator without "free capabilities", in chunks for the other
 *  QL_FIXED_ALLOC_CHUNK_NUM_BITS - only for allocator with "free-element" capabilities, defines bits count in an unsigned int number
 *  QL_FIXED_ALLOC_FOREACH_REQUIRED - specifies that foreach function is required
 *  QL_FIXED_ALLOC_CLEAR_REQUIRED - specifies that allocator_clear is required
 *
 * unmasked types/functions:
 *  Allocator
 *  InternalChunk
 *  alloc_elem
 *  free_elem
 *  init_allocator
 *  uninit_allocator
 *  get_allocator_status
 *  internal_create_allocator
 *  internal_alloc_elem_from_chunk
 *  internal_find_free_elem
 *  internal_get_bits_count         - get bits count from the number given, to be removed to the separate header
 *  get_allocator_status
 *  allocator_foreach
 *  allocator_clear
 *
 *
 * A. Shabanov, 2008-2009
 */

/*
 sample usage:

    // define type names
    #define QL_FIXED_ALLOC_NS(n)            int_##n
    #define QL_FIXED_ALLOC_ELEMENT_TYPE     int
    #define QL_FIXED_ALLOC_XMALLOC          xmalloc
    #define QL_FIXED_ALLOC_XFREE            xfree
    #define QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE (256)
    #define QL_FIXED_ALLOC_GET_ALLOCATOR_STATUS_REQUIRED
    #define QL_FIXED_ALLOC_FREE_FUNCTION_REQUIRED

    #include <qltemplates/fixed_alloc.h>

    ...
    int_Allocator        intAllocator;
    int * num;
    size_t used, allocated;

    int_init_allocator(&intAllocator);

    num = int_alloc_elem(&intAllocator);
    int_free_elem(&intAllocator, num);
    
    int_get_allocator_status(&intAllocator, &used, &allocated);
    
    int_uninit_allocator(&intAllocator);
 */

#include <string.h>


/*
 * name specifier that originates the name
 */
#ifndef QL_FIXED_ALLOC_NS
#define QL_FIXED_ALLOC_NS(name) name
#endif

/*
 * imported types
 */

#ifndef QL_FIXED_ALLOC_ELEMENT_TYPE
#error QL_FIXED_ALLOC_ELEMENT_TYPE is not defined
#endif

/*
 * imported functions
 */

#ifndef QL_FIXED_ALLOC_ASSERT
#include <assert.h>
#define QL_FIXED_ALLOC_ASSERT(condition) assert(condition)
#endif

#ifndef QL_FIXED_ALLOC_XMALLOC
#error QL_FIXED_ALLOC_XMALLOC is not defined
#endif

#ifndef QL_FIXED_ALLOC_XFREE
#error QL_FIXED_ALLOC_XFREE is not defined
#endif

/*
 * initial cache size
 */

#ifndef QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE
#define QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE   (1024)
#endif

#ifndef QL_FIXED_ALLOC_FREE_FUNCTION_REQUIRED

/* free element function is not needed */

/*
 * allocator context type definition
 */
typedef struct QL_FIXED_ALLOC_NS(InternalChunk)
{
    QL_FIXED_ALLOC_ELEMENT_TYPE   arr[QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE];
    size_t               size;
    struct QL_FIXED_ALLOC_NS(InternalChunk) * prev;
} QL_FIXED_ALLOC_NS(InternalChunk);

typedef struct QL_FIXED_ALLOC_NS(Allocator)
{
    QL_FIXED_ALLOC_NS(InternalChunk) * chunk;
} QL_FIXED_ALLOC_NS(Allocator);

static QL_FIXED_ALLOC_NS(InternalChunk) *
QL_FIXED_ALLOC_NS(internal_create_chunk)(QL_FIXED_ALLOC_NS(InternalChunk) * prev)
{
    QL_FIXED_ALLOC_NS(InternalChunk) * chunk = QL_FIXED_ALLOC_XMALLOC(sizeof(QL_FIXED_ALLOC_NS(InternalChunk)));
    chunk->size = 0;
    chunk->prev = prev;

    return chunk;
}

static void
QL_FIXED_ALLOC_NS(init_allocator)(QL_FIXED_ALLOC_NS(Allocator) * allocator)
{
    allocator->chunk = NULL;
}

static void
QL_FIXED_ALLOC_NS(uninit_allocator)(QL_FIXED_ALLOC_NS(Allocator) * allocator)
{
    QL_FIXED_ALLOC_NS(InternalChunk) * chunk = allocator->chunk;
    while (NULL != chunk)
    {
        QL_FIXED_ALLOC_NS(InternalChunk) * prev = chunk->prev;
        QL_FIXED_ALLOC_XFREE(chunk);
        chunk = prev;
    }
}

static QL_FIXED_ALLOC_ELEMENT_TYPE *
QL_FIXED_ALLOC_NS(alloc_elem)(QL_FIXED_ALLOC_NS(Allocator) * allocator)
{
    QL_FIXED_ALLOC_NS(InternalChunk) * chunk = allocator->chunk;

    if (chunk == 0 || chunk->size >= QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE)
    {
        chunk = QL_FIXED_ALLOC_NS(internal_create_chunk)(chunk);
        allocator->chunk = chunk;
    }

    return &chunk->arr[chunk->size ++];
}

#ifdef QL_FIXED_ALLOC_GET_ALLOCATOR_STATUS_REQUIRED
static void
QL_FIXED_ALLOC_NS(get_allocator_status)(QL_FIXED_ALLOC_NS(Allocator) * allocator, size_t * used, size_t * allocated)
{
    QL_FIXED_ALLOC_NS(InternalChunk) * c = allocator->chunk;

    *used = 0;
    *allocated = 0;

    while (NULL != c)
    {
        *used += c->size;
        *allocated += QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE;

        c = c->prev;
    }
}
#endif // QL_FIXED_ALLOC_GET_ALLOCATOR_STATUS_REQUIRED

#ifdef QL_FIXED_ALLOC_FOREACH_REQUIRED

static void
QL_FIXED_ALLOC_NS(allocator_foreach)(QL_FIXED_ALLOC_NS(Allocator) * allocator, void * context,
                                     void (* foreach_callback)(void * context, QL_FIXED_ALLOC_ELEMENT_TYPE * e))
{
    QL_FIXED_ALLOC_NS(InternalChunk) * c = allocator->chunk;

    while (NULL != c)
    {
        size_t i;

        for (i = 0; i < c->size; ++i)
        {
            foreach_callback(context, &c->arr[i]);
        }

        c = c->prev;
    }
}

#endif // QL_FIXED_ALLOC_FOREACH_REQUIRED

#else // QL_FIXED_ALLOC_FREE_FUNCTION_REQUIRED defined

#include <limits.h>

#ifndef QL_FIXED_ALLOC_CHUNK_NUM_BITS
#define QL_FIXED_ALLOC_CHUNK_NUM_BITS   (sizeof(unsigned int) * CHAR_BIT)
#endif

typedef struct QL_FIXED_ALLOC_NS(InternalChunk)
{
    unsigned int                free_mask;
    QL_FIXED_ALLOC_ELEMENT_TYPE arr[QL_FIXED_ALLOC_CHUNK_NUM_BITS];
} QL_FIXED_ALLOC_NS(InternalChunk);



typedef struct QL_FIXED_ALLOC_NS(InternalChunkCluster)
{
    struct QL_FIXED_ALLOC_NS(InternalChunkCluster) *    prev;
    
    /*
     * heuristic parameter:
     * determines nearest free chunk's index in this block
     */
    size_t                                              nfc_index;

    QL_FIXED_ALLOC_NS(InternalChunk)                    chunks[1];
} QL_FIXED_ALLOC_NS(InternalChunkCluster);

typedef struct QL_FIXED_ALLOC_NS(Allocator)
{
    QL_FIXED_ALLOC_NS(InternalChunkCluster) * cluster;
} QL_FIXED_ALLOC_NS(Allocator);

static void
QL_FIXED_ALLOC_NS(init_allocator)(QL_FIXED_ALLOC_NS(Allocator) * allocator)
{
    allocator->cluster = NULL;
}

static void
QL_FIXED_ALLOC_NS(uninit_allocator)(QL_FIXED_ALLOC_NS(Allocator) * allocator)
{
    QL_FIXED_ALLOC_NS(InternalChunkCluster) * c = allocator->cluster;
    while (NULL != c)
    {
        QL_FIXED_ALLOC_NS(InternalChunkCluster) * prev = c->prev;
        QL_FIXED_ALLOC_XFREE(c);
        c = prev;
    }
}


static QL_FIXED_ALLOC_ELEMENT_TYPE *
QL_FIXED_ALLOC_NS(internal_alloc_elem_from_chunk)(QL_FIXED_ALLOC_NS(InternalChunk) * chunk)
{
    size_t i;
    unsigned int mask = 1;

    QL_FIXED_ALLOC_ASSERT(chunk->free_mask != UINT_MAX);
    
    for (i = 0; i < QL_FIXED_ALLOC_CHUNK_NUM_BITS; ++i)
    {
        if (0 == (chunk->free_mask & mask))
        {
            // mark place as busy
            chunk->free_mask |= mask;
            return &chunk->arr[i];
        }

        mask = mask << 1;
    }

    QL_FIXED_ALLOC_ASSERT(!"should never come here");
    return 0;
}

static QL_FIXED_ALLOC_ELEMENT_TYPE *
QL_FIXED_ALLOC_NS(internal_find_free_elem)(QL_FIXED_ALLOC_NS(InternalChunkCluster) * cluster)
{
    for (; cluster != NULL; cluster = cluster->prev)
    {
        size_t i;
        
        for (i = cluster->nfc_index; i < QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE; ++ i)
        {
            QL_FIXED_ALLOC_NS(InternalChunk) * chunk = &cluster->chunks[i];
            if (chunk->free_mask != UINT_MAX)
            {
                // free chunk has been found!
                QL_FIXED_ALLOC_ELEMENT_TYPE * result = QL_FIXED_ALLOC_NS(internal_alloc_elem_from_chunk)(chunk);
                
                // update `last free chunk index' for this block if
                // it pointed for this block before
                if (chunk->free_mask == UINT_MAX && cluster->nfc_index == i)
                {
                    cluster->nfc_index = i + 1;
                }

                return result;
            }
        }
    }

    return NULL;
}

static QL_FIXED_ALLOC_ELEMENT_TYPE *
QL_FIXED_ALLOC_NS(alloc_elem)(QL_FIXED_ALLOC_NS(Allocator) * allocator)
{
    QL_FIXED_ALLOC_ELEMENT_TYPE * result;
    QL_FIXED_ALLOC_NS(InternalChunkCluster) * cluster = allocator->cluster;

    result = QL_FIXED_ALLOC_NS(internal_find_free_elem)(cluster);
    if (NULL == result)
    {
        // need to allocate one another block (all the blocks busy)
        size_t s = sizeof(QL_FIXED_ALLOC_NS(InternalChunkCluster)) +
            (QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE - 1) * sizeof(QL_FIXED_ALLOC_NS(InternalChunk));
        QL_FIXED_ALLOC_NS(InternalChunkCluster) * new_cluster = QL_FIXED_ALLOC_XMALLOC(s);
        
        memset(new_cluster, 0, s);
        new_cluster->prev = cluster;
        allocator->cluster = new_cluster;

        // since new block is allocated - the following function must succeed
        result = QL_FIXED_ALLOC_NS(internal_find_free_elem)(new_cluster);
        QL_FIXED_ALLOC_ASSERT(result != 0);
    }

    return result;
}

/*
 * removes one element
 */
static void
QL_FIXED_ALLOC_NS(free_elem)(QL_FIXED_ALLOC_NS(Allocator) * allocator, QL_FIXED_ALLOC_ELEMENT_TYPE * elem)
{
    const void *    p = elem;
    QL_FIXED_ALLOC_NS(InternalChunkCluster) * cluster = allocator->cluster;
    QL_FIXED_ALLOC_NS(InternalChunk) * chunk;
    size_t          chunk_index;
    size_t          arr_index;

    // find block the given list belongs to
    for (; cluster != NULL; cluster = cluster->prev)
    {
        void * left = cluster;
        void * right = (char *)cluster + sizeof(QL_FIXED_ALLOC_NS(InternalChunkCluster)) +
            (QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE - 1) * sizeof(QL_FIXED_ALLOC_NS(InternalChunk));
        
        if ((p > left) && (p < right))
        {
            break;
        }
    }

    // block may not be null and list address shall not be less than the first one chunk entry
    QL_FIXED_ALLOC_ASSERT((NULL != cluster) && (p >= (const void *)&cluster->chunks[0].arr[0]));

    // get chunk index
    chunk_index = (((size_t)p) - ((size_t)cluster->chunks)) / sizeof(QL_FIXED_ALLOC_NS(InternalChunk));
    QL_FIXED_ALLOC_ASSERT(chunk_index < QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE);

    chunk = &cluster->chunks[chunk_index];

    // now find offset in chunk arr
    arr_index = (size_t)p - (size_t)chunk->arr;
    QL_FIXED_ALLOC_ASSERT(0 == (arr_index % sizeof(QL_FIXED_ALLOC_ELEMENT_TYPE)));

    // calculate an exact index
    arr_index = arr_index / sizeof(QL_FIXED_ALLOC_ELEMENT_TYPE);
    QL_FIXED_ALLOC_ASSERT(arr_index < QL_FIXED_ALLOC_CHUNK_NUM_BITS);

    // so at last index found - re-check that
    QL_FIXED_ALLOC_ASSERT(chunk->arr + arr_index == elem);

    // check that element is not released twice
    QL_FIXED_ALLOC_ASSERT((chunk->free_mask & (1 << arr_index)) != 0);

    // mark this element as free
    chunk->free_mask &= ~(1 << arr_index);

    // update last free chunk index if it is needed
    if (cluster->nfc_index > chunk_index)
    {
        cluster->nfc_index = chunk_index;
    }
}

#ifdef QL_FIXED_ALLOC_GET_ALLOCATOR_STATUS_REQUIRED

static size_t
QL_FIXED_ALLOC_NS(internal_get_bits_count)(unsigned int num)
{
    size_t  result = 0;
    size_t  i;
    for (i = 0; i < QL_FIXED_ALLOC_CHUNK_NUM_BITS; ++ i)
    {
        result += (num & 1);
        num = num >> 1;
    }

    return result;
}

static void
QL_FIXED_ALLOC_NS(get_allocator_status)(QL_FIXED_ALLOC_NS(Allocator) * allocator, size_t * used, size_t * allocated)
{
    QL_FIXED_ALLOC_NS(InternalChunkCluster) * cluster;

    *used = 0;
    *allocated = 0;

    for (cluster = allocator->cluster; NULL != cluster; cluster = cluster->prev)
    {
        int i;

        *allocated += QL_FIXED_ALLOC_CHUNK_NUM_BITS * QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE;

        for (i = 0; i < QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE; ++ i)
        {
            *used += QL_FIXED_ALLOC_NS(internal_get_bits_count)(cluster->chunks[i].free_mask);
        }
    }
}
#endif // QL_FIXED_ALLOC_GET_ALLOCATOR_STATUS_REQUIRED

#ifdef QL_FIXED_ALLOC_FOREACH_REQUIRED

static void
QL_FIXED_ALLOC_NS(allocator_foreach)(QL_FIXED_ALLOC_NS(Allocator) * allocator, void * context,
                                     void (* foreach_callback)(void * context, QL_FIXED_ALLOC_ELEMENT_TYPE * e))
{
    QL_FIXED_ALLOC_NS(InternalChunkCluster) * cluster;

    for (cluster = allocator->cluster; NULL != cluster; cluster = cluster->prev)
    {
        size_t i;

        for (i = 0; i < QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE; ++ i)
        {
            QL_FIXED_ALLOC_NS(InternalChunk) * chunk = &cluster->chunks[i];

            if (chunk->free_mask != 0)
            {
                unsigned int mask = 1;
                size_t j;

                for (j = 0; j < QL_FIXED_ALLOC_CHUNK_NUM_BITS; ++j)
                {
                    if (chunk->free_mask & mask)
                    {
                        foreach_callback(context, &chunk->arr[j]);
                    }

                    mask = mask << 1;
                }
            }
        }
    }
}

#endif // QL_FIXED_ALLOC_FOREACH_REQUIRED

#endif // QL_FIXED_ALLOC_FREE_FUNCTION_REQUIRED

#ifdef QL_FIXED_ALLOC_CLEAR_REQUIRED

static void
QL_FIXED_ALLOC_NS(allocator_clear)(QL_FIXED_ALLOC_NS(Allocator) * allocator)
{
    QL_FIXED_ALLOC_NS(allocator_uninit)(allocator);
    QL_FIXED_ALLOC_NS(allocator_init)(allocator);
}

#endif

/*
 * undefine user macros
 */
#undef QL_FIXED_ALLOC_ELEMENT_TYPE
#undef QL_FIXED_ALLOC_XMALLOC
#undef QL_FIXED_ALLOC_XFREE
#undef QL_FIXED_ALLOC_NS
#undef QL_FIXED_ALLOC_FREE_FUNCTION_REQUIRED
#undef QL_FIXED_ALLOC_GET_ALLOCATOR_STATUS_REQUIRED
#undef QL_FIXED_ALLOC_INITIAL_CHUNK_SIZE
#undef QL_FIXED_ALLOC_CHUNK_NUM_BITS
#undef QL_FIXED_ALLOC_ASSERT
#undef QL_FIXED_ALLOC_FOREACH_REQUIRED
#undef QL_FIXED_ALLOC_CLEAR_REQUIRED
